<?php
//链表
class Element{
    public $data;
    public $next;

    public function __construct($data=''){
        $this->data=$data;
        $this->next=null;
    }
}

class MyList{

    public static function creatList($data=''){
        return new Element($data);//head为每0个元素
    }

    public static function addElement($head,$element){
        $cur=$head;
        while($cur->next!=null){
            $cur=$cur->next;
        }
        $cur->next=$element;
    }

    public static function insertElement(&$head,$n,$element){
        $cur=$head;

        if($n==0){//插入新的头部
           $element->next=$head;
            $head=$element;
            return;
        }

        $i=1;
        while($cur->next!=null&&$i<$n){
            $cur=$cur->next;
            $i++;
        }

        if($i<$n||$cur->next==null){
            $cur->next=$element;//在最后添加
        }else{
           $element->next=$cur->next;
            $cur->next=$element;
        }
    }

    public static function deleteElement(&$head,$n,&$r_element=''){
        $cur=$head;

        if($n==0){//如何删除的是头部
            $r_element=$head;
            echo 'the element is '.$r_element->data."</br>";
            $head=$cur->next;
            return;
        }

        $i=1;
        while($cur->next!=null&&$i<$n){
            $cur=$cur->next;
            $i++;
        }

        if($i<$n||$cur->next==null){
            $r_element=null;
            echo 'cant not delete the element!'."</br>";
        }else{
            $r_element=$cur->next;
            $cur->next=$cur->next->next;
        }
    }

    public static function searchElement($head,$n,&$r_element=''){
        $cur=$head;

        if($n==0){//查找的是头部
            $r_element=$head;
            echo 'the element is '.$r_element->data."</br>";
            return;
        }

        $i=1;
        while($cur->next!=null&&$i<$n){
            $cur=$cur->next;
            $i++;
        }

        if($i<$n||$cur->next==null){
            $r_element=null;
            echo 'cant not found the element!'."</br>";
        }else{
            $r_element=$cur->next;
            echo 'the element is '.$r_element->data."</br>";
        }
    }


    public static function updateElement(&$head,$n,$element){
        $cur=$head;

        if($n==0){//如何删除的是头部
            $element->next=$head->next;
            $head=$element;
            return;
        }


        $i=1;
        while($cur->next!=null&&$i<$n){
            $cur=$cur->next;
            $i++;
        }

        if($i<$n||$cur->next==null){
            $r_element=null;
            echo 'cant not found the element!'."</br>";
        }else{
            $element->next=$cur->next->next;
            $cur->next=$element;
        }
    }

    public static function showList($head){
        $cur=$head;
        while($cur!=null){
            echo $cur->data."</br>";
            $cur=$cur->next;
        }

        echo "*****************************</br>";
    }
}

$head=MyList::creatList('666');
MyList::addElement($head,new Element('1'));
MyList::addElement($head,new Element('2'));
MyList::addElement($head,new Element('3'));
MyList::addElement($head,new Element('4'));
MyList::addElement($head,new Element('5'));
MyList::showList($head);
//MyList::deleteElement($head,0);
//MyList::deleteElement($head,2);
//MyList::searchElement($head,0);
//MyList::updateElement($head,1,new Element('123'));
MyList::insertElement($head,0,new Element('fsdafsd'));
MyList::showList($head);

?>